Segmentation is useful in a wide range of computer vision applications, but fully automatic segmentation remains a difficult problem. There has been extensive work on image segmentation as well as the broader problem of data partitioning. See, for examples, Duda and Hart's "Pattern Classification and Scene Analysis," (John Wiley and Sons: 1973), or the Proc. DIMACS Workshop on Partitioning Data Sets: With applications to psychology, vision and target tracking, I. J. Cox et al, eds (American Mathematical Society: 1994), or Jain and Dubes' "Algorithms for Clustering Data" (Prentice Hall: 1988). The goal of segmentation is to find groups of data which are both homogeneous, such that data in the same group are similar, and well separated, such that data in different groups are dissimilar. Many approaches have been proposed, which may be broadly categorized as either contour-based, region-based or a combination of both.
Contour-based methods usually attempt to partition an image based solely on local measures of dissimilarity. Conversely, region-based methods partition an image based on local measures of similarity. There has been significant progress on interactive contour-based segmentation, based upon the work of Kass et al described in an article entitled "Snakes: Active contour models," in Int. J. Computer Vision, pages 321-331 (1988) and of Blake and Zisserman described in the book entitled "Visual Reconstruction," (MIT Press: 1987). The interactive initialization of the active contour or snake near the desired boundary significantly reduces the difficulty of segmentation. However, there are several difficulties with the method, including sensitivity of the final solution to the initialization and computational requirements. Cohen, in an article entitled "Note on active contour models and balloons," in CVGIP: Image Understanding, vol. 53(2), pages 211-218 (March 1991), introduced a "balloon force" which can either inflate or deflate the contour. The purpose and effect of the "balloon force" are similar to the interior area denominator term of the novel ratio cost discussed later. Amini et al, in an article entitled "Using dynamical programming for minimizing the energy of active contour in the presence of hard constraints," in Proc. Inter. Conf. on Computer Vision (ICCV), pages 95-99 (1988), proposed using dynamic programming as part of an iterative gradient descent procedure. Montanari, in an article entitled "On the optimal detection of curves in noisy pictures," in Communications of the ACM, vol. 15(5), pages 335-345 (1971), uses dynamic programming to detect a globally optimum path through a set of pixels. Later, Geiger at al, in an article entitled "Dynamic programming for detecting, tracking, and matching deformable contours," in IEEE Trans. Pattern Anal. and Machine Intell., vol. 17(3), pages 294-302 (1993), extended this work to accomodate greater uncertainty due to the motion of snakes. Their method finds an optimal solution in polynomial time. Nevertheless, significant computational time is still required though this could be improved substantially.
More powerful techniques attempt to use both region and boundary information in a cost function. Chakraborty et al, in an article entitled "Deformable boundary finding influenced by region homogeneity," in Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), pages 624-627 (June 1994), recognized the importance of combining contour and region based methods. They proposed a cost function that is the sum of a boundary cost and an a priori term that is provided by a region based segmentation method. Experimental results support combining region and boundary information. However, a global optimization cannot be guaranteed and a separate region segmentation must precede the combined method. Ronfard, in an article entitled "Region-based strategies for active contour models," in Int. J. Comput. Vision, vol. 13(2), pages 229-251 (1994), recently proposed a "region-based energy model for active contours" that again attempts to introduce region information into a contour-based algorithm. However, once again, optimization is difficult and may be susceptible to local minima. Leclerc, in an article entitled "Constructing simple stable descriptions for image partitioning," in Int. J. of Computer Vision, vol. 3, pages 73-102 (1989), proposed a partition process based on a minimum description length representation of both the intensity variation within a region and the enclosing boundary. Most recently, Zhu et al, in an article entitled "Region competition: Unifying snakes, region growing, energy/bayes/mdl for multi-band image segmentation," in Proc. Fifth Int. Conf. on Computer Vision, pages 416-423 (1995), attempted to unify snakes, region growing and energy/Bayes/MDL techniques. However, while these latter approaches offer powerful theoretical frameworks, it is often computationally difficult to minimize the associated cost functions.
Wu and Leahy, in an article entitled "An optimal graph theoretical approach to data clustering: theory and its application to image segmentation," in IEEE Trans. Pattern Anal. and Machine Intell., vol. 15(11), pages 1101-1113 (November 1993), describe an optimal graph theoretic approach to data clustering and their paper provides a good review of many graph based techniques. Wu and Leahy develop a cost function based on boundary cost alone.